//! Raw list head 实现
//!
//! Raw list head 的实现是 linux 的 list_head 实现.
//! 这个模块是一个非常底层的接口, 没有并发支持, 没有所有权,
//! 操作的对象都是裸指针, 所有操作均是 unsafe 的.
//! 这个模块的实现只是为了方便实现 page alloc 接口, 除非你真的知道自己在
//! 做什么, 否则别使用该接口.

#![no_std]
#![feature(offset_of)]

pub const LIST_POISON1: usize = 0xdead0100;
pub const LIST_POISON2: usize = 0xdead0200;

pub struct RawListHead<T> {
    next: *mut RawListNode<T>,
    prev: *mut RawListNode<T>,
    offset: usize,
}

impl<T> Default for RawListHead<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> RawListHead<T> {
    pub fn new() -> Self {
        let init = core::ptr::null_mut::<RawListNode<T>>();
        Self {
            next: init,
            prev: init,
            offset: 0,
        }
    }

    pub fn init_list_head(&mut self, offset: usize) {
        let ptr = self as *mut RawListHead<T> as *mut RawListNode<T>;
        unsafe {
            core::ptr::write_volatile(&mut self.next, ptr);
        }
        self.prev = ptr;
        self.offset = offset;
    }

    #[inline(always)]
    unsafe fn __list_add(
        new: &mut RawListNode<T>,
        prev: &mut RawListNode<T>,
        next: &mut RawListNode<T>,
    ) {
        next.prev = new;
        new.next = next;
        new.prev = prev;
        core::ptr::write_volatile(&mut prev.next, new);
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add(&mut self, new: &mut RawListNode<T>) {
        RawListHead::__list_add(
            new,
            (self as *mut RawListHead<T> as *mut RawListNode<T>)
                .as_mut()
                .unwrap(),
            self.next.as_mut().unwrap(),
        );
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add_tail(&mut self, new: &mut RawListNode<T>) {
        RawListHead::__list_add(
            new,
            self.prev.as_mut().unwrap(),
            (self as *mut RawListHead<T> as *mut RawListNode<T>)
                .as_mut()
                .unwrap(),
        );
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_is_last(&self, list: &mut RawListNode<T>) -> bool {
        core::ptr::eq(
            list.next as *const RawListNode<T>,
            self as *const RawListHead<T> as *const RawListNode<T>,
        )
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty(&self) -> bool {
        core::ptr::eq(
            core::ptr::read_volatile(&self.next) as *const RawListNode<T>,
            self as *const RawListHead<T> as *const RawListNode<T>,
        )
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty_careful(&self) -> bool {
        let next = self.next as *const RawListNode<T>;
        next == self as *const RawListHead<T> as *const RawListNode<T> && next == self.prev
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null(&self) -> Option<&T> {
        let next = self.next;
        if core::ptr::eq(
            next as *const RawListNode<T>,
            self as *const RawListHead<T> as *const RawListNode<T>,
        ) {
            None
        } else {
            Some(
                ((next as usize - self.offset) as *const T)
                    .as_ref()
                    .unwrap(),
            )
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null_mut(&mut self) -> Option<&mut T> {
        let next = self.next;
        if next == self as *mut RawListHead<T> as *mut RawListNode<T> {
            None
        } else {
            Some(((next as usize - self.offset) as *mut T).as_mut().unwrap())
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_mut(&mut self) -> &mut T {
        ((self.next as usize - self.offset) as *mut T)
            .as_mut()
            .unwrap()
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry(&self) -> &T {
        ((self.next as usize - self.offset) as *const T)
            .as_ref()
            .unwrap()
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry_mut(&mut self) -> &mut T {
        ((self.prev as usize - self.offset) as *mut T)
            .as_mut()
            .unwrap()
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry(&self) -> &T {
        ((self.prev as usize - self.offset) as *const T)
            .as_ref()
            .unwrap()
    }
}

#[macro_export]
macro_rules! init_raw_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        $var.init_list_head(core::mem::offset_of!($type, $($member).+));
    };
}

#[macro_export]
macro_rules! define_raw_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        let mut $var = $crate::RawListHead::<$type>::new();
        $crate::init_raw_list_head!($var, $type, $($member).+);
    };
}

pub struct RawListNode<T> {
    next: *mut RawListNode<T>,
    prev: *mut RawListNode<T>,
}

impl<T> Default for RawListNode<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> RawListNode<T> {
    pub fn new() -> Self {
        let init = core::ptr::null_mut::<RawListNode<T>>();
        Self {
            next: init,
            prev: init,
        }
    }

    #[inline(always)]
    unsafe fn init_list_node(&mut self) {
        let value = self as *mut RawListNode<T>;
        core::ptr::write_volatile(&mut self.next, value);
        self.prev = value;
    }

    #[inline(always)]
    unsafe fn __list_del(prev: &mut RawListNode<T>, next: &mut RawListNode<T>) {
        next.prev = prev;
        core::ptr::write_volatile(&mut prev.next, next);
    }

    #[inline(always)]
    unsafe fn __list_del_entry(&mut self) {
        RawListNode::__list_del(self.prev.as_mut().unwrap(), self.next.as_mut().unwrap());
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_del(&mut self) {
        self.__list_del_entry();
        self.next = LIST_POISON1 as *mut RawListNode<T>;
        self.prev = LIST_POISON2 as *mut RawListNode<T>;
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_replace(&mut self, new: &mut RawListNode<T>) {
        new.next = self.next;
        new.next.as_mut().unwrap().prev = new;
        new.prev = self.prev;
        new.prev.as_mut().unwrap().next = new;
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_replace_init(&mut self, new: &mut RawListNode<T>) {
        self.list_replace(new);
        self.init_list_node();
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_del_init(&mut self) {
        self.__list_del_entry();
        self.init_list_node();
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_move(&mut self, head: &mut RawListHead<T>) {
        self.__list_del_entry();
        head.list_add(self);
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_move_tail(&mut self, head: &mut RawListHead<T>) {
        self.__list_del_entry();
        head.list_add_tail(self);
    }

    #[inline(always)]
    unsafe fn list_next_entry_mut(&mut self, offset: usize) -> &mut T {
        ((self.next as usize - offset) as *mut T).as_mut().unwrap()
    }

    #[inline(always)]
    unsafe fn list_next_entry(&self, offset: usize) -> &T {
        ((self.next as usize - offset) as *const T)
            .as_ref()
            .unwrap()
    }

    #[inline(always)]
    unsafe fn list_prev_entry_mut(&mut self, offset: usize) -> &mut T {
        ((self.prev as usize - offset) as *mut T).as_mut().unwrap()
    }

    #[inline(always)]
    unsafe fn list_prev_entry(&self, offset: usize) -> &T {
        ((self.prev as usize - offset) as *const T)
            .as_ref()
            .unwrap()
    }
}

pub struct RawListHeadIter<'a, T> {
    prev_pos: *const RawListNode<T>,
    next_pos: *const RawListNode<T>,
    head: &'a RawListHead<T>,
}

impl<'a, T> RawListHeadIter<'a, T> {
    fn new(head: &'a RawListHead<T>) -> Self {
        let init = core::ptr::null::<RawListNode<T>>();
        Self {
            prev_pos: init,
            next_pos: init,
            head,
        }
    }
}

impl<T> RawListHead<T> {
    pub fn iter(&self) -> RawListHeadIter<T> {
        RawListHeadIter::new(self)
    }
}

impl<'a, T> Iterator for RawListHeadIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            if self.next_pos.is_null() {
                self.next_pos = self.head.next;
                return Some(self.head.list_first_entry());
            }

            let this = self.next_pos.as_ref().unwrap().next as *const RawListNode<T>;
            let end = if self.prev_pos.is_null() {
                self.head as *const RawListHead<T> as *const RawListNode<T>
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = self
                .next_pos
                .as_ref()
                .unwrap()
                .list_next_entry(self.head.offset);
            self.next_pos = self.next_pos.as_ref().unwrap().next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for RawListHeadIter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        unsafe {
            if self.prev_pos.is_null() {
                self.prev_pos = self.head.prev;
                return Some(self.head.list_last_entry());
            }

            let this = self.prev_pos.as_ref().unwrap().prev as *const RawListNode<T>;
            let end = if self.next_pos.is_null() {
                self.head as *const RawListHead<T> as *const RawListNode<T>
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = self
                .prev_pos
                .as_ref()
                .unwrap()
                .list_prev_entry(self.head.offset);
            self.prev_pos = self.prev_pos.as_ref().unwrap().prev;
            Some(val)
        }
    }
}

pub struct RawListHeadIterMut<'a, T> {
    prev_pos: *mut RawListNode<T>,
    next_pos: *mut RawListNode<T>,
    head: &'a mut RawListHead<T>,
}

impl<'a, T> RawListHeadIterMut<'a, T> {
    fn new(head: &'a mut RawListHead<T>) -> Self {
        let init = core::ptr::null_mut::<RawListNode<T>>();
        Self {
            prev_pos: init,
            next_pos: init,
            head,
        }
    }
}

impl<T> RawListHead<T> {
    pub fn iter_mut(&mut self) -> RawListHeadIterMut<T> {
        RawListHeadIterMut::new(self)
    }
}

impl<'a, T> Iterator for RawListHeadIterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            if self.next_pos.is_null() {
                self.next_pos = self.head.next;
                let this = self.head as *mut RawListHead<T>;
                return Some(this.as_mut().unwrap().list_first_entry_mut());
            }

            let this = self.next_pos.as_ref().unwrap().next as *const RawListNode<T>;
            let end = if self.prev_pos.is_null() {
                self.head as *const RawListHead<T> as *const RawListNode<T>
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = self
                .next_pos
                .as_mut()
                .unwrap()
                .list_next_entry_mut(self.head.offset);
            self.next_pos = self.next_pos.as_mut().unwrap().next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for RawListHeadIterMut<'a, T> {
    fn next_back(&mut self) -> Option<&'a mut T> {
        unsafe {
            if self.prev_pos.is_null() {
                self.prev_pos = self.head.prev;
                let this = self.head as *mut RawListHead<T>;
                return Some(this.as_mut().unwrap().list_last_entry_mut());
            }

            let this = self.prev_pos.as_ref().unwrap().prev as *const RawListNode<T>;
            let end = if self.next_pos.is_null() {
                self.head as *const RawListHead<T> as *const RawListNode<T>
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = self
                .prev_pos
                .as_mut()
                .unwrap()
                .list_prev_entry_mut(self.head.offset);
            self.prev_pos = self.prev_pos.as_mut().unwrap().prev;
            Some(val)
        }
    }
}
